//最后一块石头的重量
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> h(stones.begin(), stones.end());
        while (h.size() != 1) {
            int x = h.top();
            h.pop();
            int y = h.top();
            h.pop();
            h.push(x - y);
        }
        return h.top();
    }
};

//数据流中的第 K 大元素
class KthLargest {
    priority_queue<int, vector<int>, greater<int>> h;
    int _k;

public:
    KthLargest(int k, vector<int>& nums) {
        _k = k;
        for (auto& num : nums) {
            h.push(num);
            if (h.size() > _k) {
                h.pop();
            }
        }
    }

    int add(int val) {
        h.push(val);
        if (h.size() > _k)
            h.pop();
        return h.top();
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

 //692. 前K个高频单词
 class Solution {
public:
    typedef pair<string, int> PSI;
    struct comp {
        bool operator()(const pair<string, int> x, const pair<string, int> y) {
            if (x.second != y.second) {
                return x.second > y.second;
            }
            return x.first < y.first;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> hash;
        priority_queue<pair<string, int>, vector<PSI>, comp> h;
        for (auto& s : words)
            hash[s]++;
        for (auto& P : hash) {
            h.push(P);
            if (h.size() > k)
                h.pop();
        }
        vector<string> ret;
        while (h.size()) {
            ret.push_back(h.top().first);
            h.pop();
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};